print("树的操作")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
print("判断是不是对称二叉树")
def isSymmetric(root:TreeNode)->bool:
    def panduanzuoyouduichen(left:TreeNode,right:TreeNode)->bool:
        if not left and not right:
            return True
        if not left or not right or left.val!=right.val:
            return False
        return panduanzuoyouduichen(left.left,right.right) and panduanzuoyouduichen(left.right,right.left)

    if not root:
        return False
    return panduanzuoyouduichen(root.left,root.right)

print("判断是不是相同的树")
def isSameTree(p:TreeNode,q:TreeNode):
    if not p and not q:
        return True
    if not p or not q or p.val!=q.val:
        return False
    return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

print("二叉树的最大深度")
def maxDepth(root:TreeNode)->int:
    if not root:
        return 0
    return max(maxDepth(root.left),maxDepth(root.right))+1

print("判断是不是平衡二叉树"
      "二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。"
      "根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，"
      "递归的顺序可以是自顶向下或者自底向上。"
      "1、每一个节点的左子结点和右子节点高度不能大于1"
      "2、每一个节点同时也是平衡二叉树"
      "3、空节点也是平衡二叉树")
def isBalanced(root:TreeNode)->bool:
    def inner_height(node:TreeNode)->int:
        if not node :
            return 0
        return max(inner_height(node.left),inner_height(node.right))+1
    if not root:
        return True
    return abs(inner_height(root.left)-inner_height(root.right))<=1 and isBalanced(root.left) and isBalanced(root.right)

print("树的最小深度")
def minDepth(root:TreeNode)->int:
    if not root:
        return 0
    if not root.left:
        return minDepth(root.right)+1
    if not root.right:
        return minDepth(root.left)+1
    return min(minDepth(root.left),minDepth(root.right))+1

print("路径总和"
      "判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。"
      "如果存在，返回 true ；否则，返回 false 。")
def lujingzonghe(root:TreeNode,targetSum:int)->bool:
    if not root:
        return False
    targetSum=targetSum-root.val
    if not root.left and not root.right:
        return targetSum==0
    return lujingzonghe(root.left,targetSum) or lujingzonghe(root.right,targetSum)

print("二叉树的前序遍历、中序遍历、后序遍历")
def qianxubianli(root:TreeNode)->list[int]:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return
        res.append(node.val)
        inner(node.left)
        inner(node.right)
    inner(root)
    return res

def zhongxubianli(root:TreeNode)->list[int]:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return
        inner(node.left)
        res.append(node.val)
        inner(node.right)
    inner(root)
    return res

def houxubianli(root:TreeNode)->list[int]:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return
        inner(node.left)
        inner(node.right)
        res.append(node.val)
    inner(root)
    return res


print("完全二叉树的节点个数")
def countNodes(root:TreeNode) ->int:
    if not root:
        return 0
    return countNodes(root.left)+countNodes(root.right)+1

print("反转二叉树")
def fanzhuanerchashu(root:TreeNode)->TreeNode:
    if not root:
        return None
    left = fanzhuanerchashu(root.left)
    right = fanzhuanerchashu(root.right)
    root.left=right
    root.right=left
    return root

print("给定二叉树的根节点 root ，返回所有左叶子之和")
def zuoyezihe(root:TreeNode)->int:
    sum=0
    def inner(node:TreeNode):
        if not node:
            return 0
        if node.left and not node.left.left and not node.left.right:
            nonlocal sum
            sum=sum+node.left.val
        inner(node.left)
        inner(node.right)
    inner(root)
    return sum
print("链表操作")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=0
        self.next=next
print("回文链表")
def huiwenlianbiao(head:ListNode)->bool:
    if not head:
        return False
    current=head
    temp_list=[]
    while current:
        temp_list.append(current.val)
        current=current.next
    return temp_list==temp_list[::-1]

print("返回相交链表的相交节点")
def xiangjiaojiedian(headA:ListNode,headB:ListNode)->ListNode:
    if not headA or not headB:
        return None
    current=headA
    temp_list=[]
    while current:
        temp_list.append(current)
        current=current.next
    current=headB
    while current:
        if current in temp_list:
            return current
        current=current.next
    return None

print("反转链表")
def fanzhuanlianbiao(head:ListNode)->ListNode:
    if not head:
        return None
    pre=None
    current=head
    while current:
        temp=current.next
        current.next=pre
        pre=current
        current=temp
    return pre

print("移除链表元素"
      "给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点")
def yichulianbiaoyuansu(head:ListNode,val:int)->ListNode:
    if not head:
        return None
    new_head=ListNode()
    new_head.next=head
    current=new_head
    while current.next:
        if current.next.val==val:
            current.next=current.next.next
        else:
            current=current.next
    return new_head.next

print("判断是不是环形链表")
def huanxinglianbiao(head:ListNode)->bool:
    if not head:
        return False
    fast=head
    slow=head
    while fast:
        if not fast.next or not fast.next.next:
            return False
        fast = fast.next.next
        slow=slow.next
        if fast==slow:
            return True
    return False

print("删除排序链表中的重复元素")
def shanchuchongfuyuansu(head:ListNode)->ListNode:
    if not head:
        return None
    current=head
    while current.next:
        if current.val==current.next.val:
            current.next=current.next.next
        else:
            current=current.next
    return head

print("非数、非链表操作")
print("重复的子字符串"
      "给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成")
def chongfuzizifuchuan(s:str)->bool:
    for i in range(1,len(s)):
        if len(s)%len(s[0:i])==0:
            count=len(s)//len(s[0:i])
            temp=s[::]
            for j in range(0,count):
                temp=temp.replace(s[0:i],"")
            if len(temp)==0:
                return True
    return False

print("分发饼干"
      "对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。"
      "如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，"
      "并输出这个最大数值")
def fenfabinggan(g:list[int],s:list[int])->int:
    child_index,cookie_index=0,0
    g.sort()
    s.sort()
    while child_index<len(g) and cookie_index<len(s):
        if s[cookie_index]>=g[child_index]:
            child_index+=1
            cookie_index+=1
        else:
            cookie_index+=1
    return child_index

print("找到所有的从数组中消失的数字"
      "给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范"
      "围内但没有出现在 nums 中的数字，并以数组的形式返回结果")
def xiaoshishuzi(nums:list[int])->list[int]:
    res=[]

    # 超时
    # for i in range(1,len(nums)+1):
    #     if i not in nums:
    #         res.append(i)
    # return res
    import collections
    counter=collections.Counter(nums)
    for i in range(1,len(nums)+1):
        if counter[i]==0:
            res.append(i)
    return res


print("排列硬币-返回完整阶梯行")
def wanzhengjieti(n:int)->int:
    if n==0:
        return 0
    sum=0
    for i in range(1,n+1):
        sum=sum+i
        if sum==n:
            return i
        if sum>n:
            return i-1

print("返回字符串中的单词数"
      "这里的单词指的是连续的不是空格的字符")
def dancishu(s:str)->int:
    return len(s.split())

print("字符串相加")
def strxiangjia(num1:str,num2:str)->str:
    list_1=list(num1)
    list_2=list(num2)
    one_index=len(list_1)-1
    two_index=len(list_2)-1
    jinwei=0
    res=""
    while one_index>=0 or two_index>=0:
        n1=int(list_1[one_index]) if one_index>=0 else 0
        n2=int(list_2[two_index]) if two_index>=0 else 0
        temp=n1+n2+jinwei
        res=str(temp%10)+res
        jinwei = temp//10
        one_index-=1
        two_index-=1
    return str(jinwei)+res if jinwei>0 else res

print("返回最长回文串")
def zuichanghuiwenchuan(s:str)->int:
    import collections
    counter=collections.Counter(s)
    res=0
    flag=0
    for k,v in counter.items():
        if v%2==0:
            res+=v
        else:
            res+=(v//2)*2
            flag=1
    return res+flag
print("s" in "ss")
print("判断子序列 判断s是否是t的子序列"
      "字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。"
      "（例如，'ace'是'abcde'的一个子序列，而'aec'不是）")
def zixulie(s:str,t:str)->bool:
    if not s:
        return True
    # current_index=0
    # for tt in t:
    #     if tt==s[current_index]:
    #         current_index+=1
    #         if current_index==len(s):
    #             return True
    # return False
    for ss in s:
        temp=t.find(ss)
        if temp<0:
            return False
        t=t[temp+1::]
    return True
s="aaaaaa"
t="bbaaaa"
print(zixulie(s,t))


print("找不同找出随机添加的字符串 "
      "字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。"
      "请找出在 t 中被添加的字母。")
def finddiff(s:str,t:str)->str:
    import collections
    return list((collections.Counter(t)-collections.Counter(s)))[0]

print("给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1")
def findfirstchar(s:str)->int:
    import collections
    # counter=collections.Counter(s)
    # for index,value in enumerate(s):
    #     if counter[value]==1:
    #         return index
    # return -1
    # temp_dict=dict(collections.Counter(s))
    # temp_dict=dict(sorted(temp_dict.items(),key=lambda item:item[1]))
    # print(temp_dict)
    # print(temp_dict.keys())
    # print(list(temp_dict.keys()))
    # if temp_dict[list(temp_dict.keys())[0]]==1:
    #     print(list(temp_dict.keys())[0])
    #     return s.index(list(temp_dict.keys())[0])
    # return -1

    temp_dict=dict(collections.Counter(s))
    from operator import itemgetter
    temp_dict=dict(sorted(temp_dict.items(),key=itemgetter(1)))
    if temp_dict[list(temp_dict.keys())[0]]==1:
        return s.index(list(temp_dict.keys())[0])
    return -1

# s="loveleetcode"
s="leetcode"
findfirstchar(s)

print("给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成"
      "magazine 中的每个字符只能在 ransomNote 中使用一次")
def canconstruct(ransomNote:str,magazine:str)->bool:
    import collections
    # counter=collections.Counter(magazine)
    # for r in ransomNote:
    #     counter[r]=counter[r]-1
    #     if counter[r]<0:
    #         return False
    # return True
    r_counter=collections.Counter(ransomNote)
    m_counter=collections.Counter(magazine)
    for r in ransomNote:
        if r_counter[r]>m_counter[r]:
            return False
    return True

print("二分法猜数字大小"
      "我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字")
def guess(num:int)->bool:
    pass
def guessnumber(n:int)->int:
    left,right=1,n
    while left<=right:
        temp=(left+right)//2
        if guess(temp)==0:
            return temp
        elif guess(temp)>0:
            left=temp+1
        else:
            right=temp-1
    return -1

print("有效的完全平方数")
def youxiaowanquanpingfangshu(num:int)->bool:
    for i in range(1,num+1):
        if i**2==num:
            return True
        if (i+1)**2>num:
            return False

print("两个数组的交集"
      "给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。"
      "返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数"
      "一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。")
def intersect(nums1:list,nums2:list)->list[int]:
    # import collections
    # return list(((collections.Counter(nums1))&(collections.Counter(nums2))).elements())
    res=[]
    for n1 in nums1:
        if n1 in nums2 and n1 not in res:
            count_1=nums1.count(n1)
            count_2=nums2.count(n1)
            count=min(count_1,count_2)
            for i in range(0,count):
                res.append(n1)
    return res

print("两个数组的交集"
      "每个元素只出现一次")
def intersect2(nums1:list[int],nums2:list[int])->list[int]:
    # import collections
    # return list((collections.Counter(nums1))&(collections.Counter(nums2)))
    # return list(set(nums1).intersection(set(nums2)))
    res=[]
    for n1 in nums1:
        if n1 in nums2 and n1 not in res:
            res.append(n1)
    return res

print("反转字符串中的元音字母"
      "只有两个索引位置的值都是原因字母时才翻转")
def fanzhuanyuanyin(s:str)->str:
    # left,right=0,len(s)-1
    # yuanyin="aeiouAEIOU"
    # s_list=list(s)
    # while left<=right:
    #     if s_list[left] not in yuanyin:
    #         left+=1
    #         continue
    #     if s_list[right] not in yuanyin:
    #         right-=1
    #         continue
    #     s_list[left],s_list[right]=s_list[right],s_list[left]
    #     left+=left
    #     right-=right
    # return "".join(s_list)
    s_list=list(s)
    yuanyin = "aeiouAEIOU"
    temp_list=[]
    for index,val in enumerate(s):
        if val in yuanyin:
            temp_list.append(index)
    for i in range(0,len(temp_list)//2):
        s_list[temp_list[i]],s_list[temp_list[len(temp_list)-1-i]]=s_list[temp_list[len(temp_list)-1-i]],s_list[temp_list[i]]
    return "".join(s_list)

print("不额外分配空间翻转字符串")
def fanzhuanstr(s:list[str])->list[str]:
    for i in range(0,len(s)//2):
        s[i],s[len(s)-1-i]=s[len(s)-1-i],s[i]
    return s


print("4的幂")
def mi_4(n:int)->bool:
    if n<=0:
        return False
    if n==1:
        return True
    res=1
    for i in range(0,n):
        res=4*res
        if res==n:
            return True
        if res >n:
            return False

print("3的幂")
def mi_3(n:int)->bool:
    if n<=1:
        return n==1
    res=1
    for i in range(0,n):
        res=res*3
        if res==n:
            return True
        if res>n:
            return False

print("nim游戏")
def nim(n:int)->bool:
    return not n%4==0

print("单词规律"
      "给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律"
      "pattern = 'abba', s = 'dog cat cat dog'")
def danciguilv(pattern:str,s:str)->bool:
    p_list=list(pattern)
    s_list=list(s.split())
    if len(p_list)!=len(s_list):
        return False
    p_map={}
    s_map={}
    for p,s in zip(p_list,s_list):
        if p in p_map:
            if p_map[p]!=s:
                return False
        else:
            p_map[p]=s
        if s in s_map:
            if s_map[s]!=p:
                return False
        else:
            s_map[s]=p
    return True

s = 'dog,.cat,.cat,dog'
print(s.split(",."))

print("移动0"
      "编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序")
test_num=[0,0,1,2,3]
test_num.remove(0)
print(test_num)
def yidong0(nums:list[int])->list[int]:
    count=nums.count(0)
    for c in range(0,count):
        nums.remove(0)
        nums.append(0)
    return nums

print("第一个错误版本")
def isBadVersion(i:int)->bool:
    pass
def firstbadversion(n:int)->int:
    left,right=1,n
    while left<=right:
        mid=(left+right)//2
        if isBadVersion(mid):
            right=mid-1
        else:
            left=mid+1
    return left

print("丢失的数字"
      "给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数")
def diushideshuzi(nums:list[int])->int:
    # for i in range(0,len(nums)+1):
    #     if i not in nums:
    #         return i
    import collections
    counter=collections.Counter(nums)
    for i in range(0,len(nums)+1):
        if counter[i]==0:
            return i

print("判断是不是丑数")
def choushu(n:int)->bool:
    if n<=1:
        return n==1
    for t in [2,3,5]:
        while n%t==0:
            n=n/t
    return n==1

print("各位相加"
      "给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果")
def geweixiangjia(num:int)->int:
    if num<10:
        return num
    while num>9:
        temp_list =[int(t) for t in list(str(num))]
        he=sum(temp_list)
        if he<10:
            return he
        else:
            num=he


print("有效的字母异位词"
      "字母异位词 是通过重新排列不同单词或短语的字母而形成的单词或短语，通常只使用所有原始字母一次"
      "判断 t 是否是 s 的字母异位词  "
      "其实就是判断两个字符串长度是否相等  如果相等的话 两个字符串中每个字符出现的次数相等")
def yiweici(s:str,t:str)->bool:
    # import collections
    # counter_1=collections.Counter(s)
    # counter_2=collections.Counter(t)
    # return len(counter_1-counter_2)==0 and len(counter_2-counter_1)==0
    if len(s) != len(t):
        return False
    for ss in s:
        if s.count(ss) != t.count(ss):
            return False
    return True

print("2的幂")
def mi_2(n:int)->bool:
    if n<=1:
        return n==1
    res=1
    for i in range(0,n):
        res=res*2
        if res==n:
            return True
        if res>n:
            return False

print("存在重复元素 - 002"
      "给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，"
      "满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false ")
def chongfuyuansu02(nums:list[int],k:int)->bool:
    temp_dict={}
    for index,val in enumerate(nums):
        if val in temp_dict:
            if abs(temp_dict[val]-index)<=k:
                return True
        temp_dict[val]=index
    return False

print("存在重复元素 - 001"
      "简单的判断数组中是否有重复元素")
def chognfuyuansu01(nums:list[int])->bool:
    # return len(set(nums))==len(nums)
    import collections
    counter_dict=dict(collections.Counter(nums))
    res_dict=dict(sorted(counter_dict.items(),key=lambda item:item[1],reverse=True))
    return res_dict[list(res_dict.keys())[0]]>1

    # print(counter_dict)
    # 默认排序是按元素个数升序
    # res_dict=dict(sorted(counter_dict.items(),key=lambda item:item[1]))

    # 默认排序是按元素个数升序
    # from operator import itemgetter
    # res_dict=dict(sorted(counter_dict.items(),key=itemgetter(1),reverse=True))
    # print(res_dict)

nums = ["a","b","a","c"]
chognfuyuansu01(nums)


print("给定两个字符串，判定他们是否是同构字符串"
      "s = 'egg', t = 'add'")
def tonggouzifuchuan(s:str,t:str)->bool:
    s_list=list(s)
    t_list=list(t)
    if len(s_list)!=len(t_list):
        return False
    s_map={}
    t_map={}
    for ss,tt in zip(s_list,t_list):
        if ss in s_map:
            if s_map[ss]!= tt:
                return False
        else:
            s_map[ss]=tt
        if tt in t_map:
            if t_map[tt]!=ss:
                return False
        else:
            t_map[tt]=ss
    return True


print("判断是不是快乐数"
      "正整数各个位上的数的平方反复相加，看最终结果是否能等于1")
def kuaileshu(n:int)->bool:
    if n<10:
        return n==1
    cached_list=[]
    while True:
        he=sum([int(l)**2 for l in list(str(n))])
        if he==1:
            return True
        if he in cached_list:
            return False
        cached_list.append(he)
        n=he

print("判断是不是多数元素"
      "给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素")
def duoshuyuansu(nums:list[int])->int:
    import collections
    counter=collections.Counter(nums)
    flag=len(nums)/2
    for k,v in counter.items():
        if v>flag:
            return k

print("只出现一次的元素"
      "给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素")
def zhichuxainyiciyuansu(nums:list[int])->int:
    # import collections
    # counter=collections.Counter(nums)
    # for k,v in counter.items():
    #     if v==1:
    #         return k
    import collections
    counter_dict=dict(collections.Counter(nums))
    # tem_list=dict(sorted(counter_dict.items(),key=lambda item:item[1]))
    from operator import itemgetter
    tem_list=dict(sorted(counter_dict.items(),key=itemgetter(1)))
    return list(tem_list.keys())[0]


print("验证回文串"
      "如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。"
      "则可以认为该短语是一个 回文串"
      "字母和数字都属于字母数字字符"
      "s = 'A man, a plan, a canal: Panama'")
def yanzhenghuiwenchuan(s:str)->bool:
    tem_list=[]
    for ss in s:
        if ss.isalpha():
            tem_list.append(ss.lower())
        if ss.isdigit():
            tem_list.append(ss)
    return tem_list==tem_list[::-1]

print("买卖股票的最佳时机")
def maimaigupiao(prices:list[int])->int:
    profit=0
    min_price=prices[0]
    for p in prices:
        min_price=min(min_price,p)
        profit=max(profit,p-min_price)
    return profit

print("给定一个非负整数n，返回杨辉三角的前n行")
def yanghuisanjiao001(numRows:int)->list[list[int]]:
    source_list=[[1]*i for i in range(1,numRows+1)]
    if numRows <=2:
        return source_list
    for i in range(0,len(source_list)):
        if i>1:
            for j in range(1,len(source_list[i])-1):
                source_list[i][j]=source_list[i-1][j-1]+source_list[i-1][j]
    return source_list

print("给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行")
def yanghuisanjiao002(rowIndex:int)->list[int]:
    source_list=[[1]*(i+1) for i in range(0,rowIndex+1)]
    if rowIndex<=1:
        return source_list[rowIndex]
    for i in range(2,len(source_list)+1):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j]=source_list[i-1][j-1]+source_list[i-1][j]
    return source_list[rowIndex]


print("爬楼梯")
def palouti(n:int)->int:
    if n==0 or n==1:
        return 1
    return palouti(n-1)+palouti(n-2);


def palouti2(n:int)->int:
    res=[1,2]
    if n<=2:
        return res[-1]
    if len(res)<n:
        res= res[-1]+res[-2]
    return res[-1]

print("X的算数平方根"
      "给你一个非负整数 x,由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去")
def suanshupingfanggen(x:int)->int:
    if x<=1:
        return x
    for i in range(1,x):
        if i**2==x or (i+1)**2>x:
            return i











